package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/'>找出字符串的可整除数组(Find the Divisibility Array of a String)</a>
 * <p>给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。</p>
 * <p>
 * word 的 可整除数组 div  是一个长度为 n 的整数数组，并满足：
 *     <ul>
 *         <li>如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1</li>
 *         <li>否则，div[i] = 0</li>
 *     </ul>
 * </p>
 * <p>返回 word 的可整除数组。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：word = "998244353", m = 3
 *      输出：[1,1,0,0,0,1,1,0,0]
 *      解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。
 *
 * 示例 2：
 *      输入：word = "1010", m = 10
 *      输出：[0,1,0,1]
 *      解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= n <= 10^5</li>
 *      <li>word.length == n</li>
 *      <li>word 由数字 0 到 9 组成</li>
 *      <li>1 <= m <= 10^9</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/7 9:49
 */
public class LC2575FindTheDivisibilityArrayOfString_M {
    static class Solution {
        public int[] divisibilityArray(String word, int m) {
            int length = word.length();
            int[] ans = new int[length];
            long val = 0;
            char[] chars = word.toCharArray();
            for (int i = 0; i < length; i++) {
                val = (val * 10 + (chars[i] - '0')) % m;
                if (val == 0) {
                    ans[i] = 1;
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.divisibilityArray("998244353", 3));
        Printer.printArrayInt(solution.divisibilityArray("1010", 10));
        Printer.printArrayInt(solution.divisibilityArray("4868438856666666", 6));
        Printer.printArrayInt(solution.divisibilityArray("91221181269244172125025075166510211202115152121212341281327", 21));
    }
}
